home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / idict.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  24.2 KB  |  813 lines
  1. /* Copyright (C) 1989, 1996, 1997, 1998, 1999, 2000 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: idict.c,v 1.2.2.1 2000/11/30 18:30:25 rayjj Exp $ */
  20. /* Dictionary implementation */
  21. #include "math_.h"        /* for frexp */
  22. #include "string_.h"        /* for strlen */
  23. #include "ghost.h"
  24. #include "gxalloc.h"        /* for accessing masks */
  25. #include "errors.h"
  26. #include "imemory.h"
  27. #include "idebug.h"        /* for debug_print_name */
  28. #include "inamedef.h"
  29. #include "iname.h"
  30. #include "ipacked.h"
  31. #include "isave.h"        /* for value cache in names */
  32. #include "store.h"
  33. #include "idict.h"        /* interface definition */
  34. #include "idictdef.h"
  35. #include "iutil.h"
  36. #include "ivmspace.h"        /* for store check */
  37.  
  38. /*
  39.  * Dictionaries per se aren't supposed to know anything about the
  40.  * dictionary stack, let alone the interpreter's dictionary stack.
  41.  * Unfortunately, there is are two design couplings between them:
  42.  * dictionary stacks cache some of the elements of their top dictionary
  43.  * (requiring updating when that dictionary grows or is unpacked),
  44.  * and names may cache a pointer to their definition (requiring a
  45.  * check whether a dictionary appears on the dictionary stack).
  46.  * Therefore, we need iddstack.h here.
  47.  * We'd really like to fix this, but we don't see how.
  48.  */
  49. #include "iddstack.h"
  50.  
  51. /*
  52.  * Define the size of the largest valid dictionary.
  53.  * This is limited by the size field of the keys and values refs,
  54.  * and by the enumeration interface, which requires the size to
  55.  * fit in an int.  As it happens, max_array_size will always be
  56.  * smaller than max_int.
  57.  */
  58. const uint dict_max_size = max_array_size - 1;
  59.  
  60. /* Define whether dictionaries expand automatically when full. */
  61. bool dict_auto_expand = false;
  62.  
  63. /* Define whether dictionaries are packed by default. */
  64. bool dict_default_pack = true;
  65.  
  66. /* Forward references */
  67. private int dict_create_contents(P3(uint size, const ref * pdref, bool pack));
  68.  
  69. /* Debugging statistics */
  70. #ifdef DEBUG
  71. struct stats_dict_s {
  72.     long lookups;        /* total lookups */
  73.     long probe1;        /* successful lookups on only 1 probe */
  74.     long probe2;        /* successful lookups on 2 probes */
  75. } stats_dict;
  76.  
  77. /* Wrapper for dict_find */
  78. int real_dict_find(P3(const ref * pdref, const ref * key, ref ** ppvalue));
  79. int
  80. dict_find(const ref * pdref, const ref * pkey, ref ** ppvalue)
  81. {
  82.     dict *pdict = pdref->value.pdict;
  83.     int code = real_dict_find(pdref, pkey, ppvalue);
  84.  
  85.     stats_dict.lookups++;
  86.     if (r_has_type(pkey, t_name) && dict_is_packed(pdict)) {
  87.     uint nidx = name_index(pkey);
  88.     uint hash =
  89.     dict_hash_mod(dict_name_index_hash(nidx), npairs(pdict)) + 1;
  90.  
  91.     if (pdict->keys.value.packed[hash] ==
  92.         pt_tag(pt_literal_name) + nidx
  93.         )
  94.         stats_dict.probe1++;
  95.     else if (pdict->keys.value.packed[hash - 1] ==
  96.          pt_tag(pt_literal_name) + nidx
  97.         )
  98.         stats_dict.probe2++;
  99.     }
  100.     /* Do the cheap flag test before the expensive remainder test. */
  101.     if (gs_debug_c('d') && !(stats_dict.lookups % 1000))
  102.     dlprintf3("[d]lookups=%ld probe1=%ld probe2=%ld\n",
  103.           stats_dict.lookups, stats_dict.probe1, stats_dict.probe2);
  104.     return code;
  105. }
  106. #define dict_find real_dict_find
  107. #endif
  108.  
  109. /* Round up the size of a dictionary.  Return 0 if too large. */
  110. uint
  111. dict_round_size_small(uint rsize)
  112. {
  113.     return (rsize > dict_max_size ? 0 : rsize);
  114. }
  115. uint
  116. dict_round_size_large(uint rsize)
  117. {                /* Round up to a power of 2 if not huge. */
  118.     /* If the addition overflows, the new rsize will be zero, */
  119.     /* which will (correctly) be interpreted as a limitcheck. */
  120.     if (rsize > dict_max_non_huge)
  121.     return (rsize > dict_max_size ? 0 : rsize);
  122.     while (rsize & (rsize - 1))
  123.     rsize = (rsize | (rsize - 1)) + 1;
  124.     return (rsize <= dict_max_size ? rsize : dict_max_non_huge);
  125. }
  126.  
  127. /* Create a dictionary using the given allocator. */
  128. int
  129. dict_alloc(gs_ref_memory_t * mem, uint size, ref * pdref)
  130. {
  131.     ref arr;
  132.     int code =
  133.     gs_alloc_ref_array(mem, &arr, a_all, sizeof(dict) / sizeof(ref),
  134.                "dict_alloc");
  135.     dict *pdict;
  136.     ref dref;
  137.  
  138.     if (code < 0)
  139.     return code;
  140.     pdict = (dict *) arr.value.refs;
  141.     make_tav(&dref, t_dictionary,
  142.          r_space(&arr) | imemory_new_mask(mem) | a_all,
  143.          pdict, pdict);
  144.     make_struct(&pdict->memory, avm_foreign, mem);
  145.     code = dict_create_contents(size, &dref, dict_default_pack);
  146.     if (code < 0) {
  147.     gs_free_ref_array(mem, &arr, "dict_alloc");
  148.     return code;
  149.     }
  150.     *pdref = dref;
  151.     return 0;
  152. }
  153. /* Create unpacked keys for a dictionary. */
  154. /* The keys are allocated using the same allocator as the dictionary. */
  155. private int
  156. dict_create_unpacked_keys(uint asize, const ref * pdref)
  157. {
  158.     dict *pdict = pdref->value.pdict;
  159.     gs_ref_memory_t *mem = dict_memory(pdict);
  160.     int code;
  161.  
  162.     code = gs_alloc_ref_array(mem, &pdict->keys, a_all, asize,
  163.                   "dict_create_unpacked_keys");
  164.     if (code >= 0) {
  165.     uint new_mask = imemory_new_mask(mem);
  166.     ref *kp = pdict->keys.value.refs;
  167.  
  168.     r_set_attrs(&pdict->keys, new_mask);
  169.     refset_null_new(kp, asize, new_mask);
  170.     r_set_attrs(kp, a_executable);    /* wraparound entry */
  171.     }
  172.     return code;
  173. }
  174. /* Create the contents (keys and values) of a newly allocated dictionary. */
  175. /* Allocate in the current VM space, which is assumed to be the same as */
  176. /* the VM space where the dictionary is allocated. */
  177. private int
  178. dict_create_contents(uint size, const ref * pdref, bool pack)
  179. {
  180.     dict *pdict = pdref->value.pdict;
  181.     gs_ref_memory_t *mem = dict_memory(pdict);
  182.     uint new_mask = imemory_new_mask(mem);
  183.     uint asize = dict_round_size((size == 0 ? 1 : size));
  184.     int code;
  185.     register uint i;
  186.  
  187.     if (asize == 0 || asize > max_array_size - 1)    /* too large */
  188.     return_error(e_limitcheck);
  189.     asize++;            /* allow room for wraparound entry */
  190.     code = gs_alloc_ref_array(mem, &pdict->values, a_all, asize,
  191.                   "dict_create_contents(values)");
  192.     if (code < 0)
  193.     return code;
  194.     r_set_attrs(&pdict->values, new_mask);
  195.     refset_null_new(pdict->values.value.refs, asize, new_mask);
  196.     if (pack) {
  197.     uint ksize = (asize + packed_per_ref - 1) / packed_per_ref;
  198.     ref arr;
  199.     ref_packed *pkp;
  200.     ref_packed *pzp;
  201.  
  202.     code = gs_alloc_ref_array(mem, &arr, a_all, ksize,
  203.                   "dict_create_contents(packed keys)");
  204.     if (code < 0)
  205.         return code;
  206.     pkp = (ref_packed *) arr.value.refs;
  207.     make_tasv(&pdict->keys, t_shortarray,
  208.           r_space(&arr) | a_all | new_mask,
  209.           asize, packed, pkp);
  210.     for (pzp = pkp, i = 0; i < asize || i % packed_per_ref; pzp++, i++)
  211.         *pzp = packed_key_empty;
  212.     *pkp = packed_key_deleted;    /* wraparound entry */
  213.     } else {            /* not packed */
  214.     int code = dict_create_unpacked_keys(asize, pdref);
  215.  
  216.     if (code < 0)
  217.         return code;
  218.     }
  219.     make_tav(&pdict->count, t_integer, new_mask, intval, 0);
  220.     make_tav(&pdict->maxlength, t_integer, new_mask, intval, size);
  221.     return 0;
  222. }
  223.  
  224. /*
  225.  * Ensure that a dictionary uses the unpacked representation for keys.
  226.  * We can't just use dict_resize, because the values slots mustn't move.
  227.  */
  228. int
  229. dict_unpack(ref * pdref, dict_stack_t *pds)
  230. {
  231.     dict *pdict = pdref->value.pdict;
  232.  
  233.     if (!dict_is_packed(pdict))
  234.     return 0;        /* nothing to do */
  235.     {
  236.     gs_ref_memory_t *mem = dict_memory(pdict);
  237.     uint count = nslots(pdict);
  238.     const ref_packed *okp = pdict->keys.value.packed;
  239.     ref old_keys;
  240.     int code;
  241.     ref *nkp;
  242.  
  243.     old_keys = pdict->keys;
  244.     if (ref_must_save_in(mem, &old_keys))
  245.         ref_do_save_in(mem, pdref, &pdict->keys, "dict_unpack(keys)");
  246.     code = dict_create_unpacked_keys(count, pdref);
  247.     if (code < 0)
  248.         return code;
  249.     for (nkp = pdict->keys.value.refs; count--; okp++, nkp++)
  250.         if (r_packed_is_name(okp)) {
  251.         packed_get(okp, nkp);
  252.         ref_mark_new_in(mem, nkp);
  253.         } else if (*okp == packed_key_deleted)
  254.         r_set_attrs(nkp, a_executable);
  255.     if (!ref_must_save_in(mem, &old_keys))
  256.         gs_free_ref_array(mem, &old_keys, "dict_unpack(old keys)");
  257.     if (pds)
  258.         dstack_set_top(pds);    /* just in case */
  259.     }
  260.     return 0;
  261. }
  262.  
  263. /*
  264.  * Look up a key in a dictionary.  Store a pointer to the value slot
  265.  * where found, or to the (value) slot for inserting.
  266.  * Return 1 if found, 0 if not and there is room for a new entry,
  267.  * or e_dictfull if the dictionary is full and the key is missing.
  268.  * The caller is responsible for ensuring key is not a null.
  269.  */
  270. int
  271. dict_find(const ref * pdref, const ref * pkey,
  272.       ref ** ppvalue /* result is stored here */ )
  273. {
  274.     dict *pdict = pdref->value.pdict;
  275.     uint size = npairs(pdict);
  276.     register int etype;
  277.     uint nidx;
  278.     ref_packed kpack;
  279.     uint hash;
  280.     int ktype;
  281.  
  282.     /* Compute hash.  The only types we bother with are strings, */
  283.     /* names, and (unlikely, but worth checking for) integers. */
  284.     switch (r_type(pkey)) {
  285.     case t_name:
  286.     nidx = name_index(pkey);
  287.     nh:
  288.     hash = dict_name_index_hash(nidx);
  289.     kpack = packed_name_key(nidx);
  290.     ktype = t_name;
  291.     break;
  292.     case t_string:        /* convert to a name first */
  293.     {
  294.         ref nref;
  295.         int code;
  296.  
  297.         if (!r_has_attr(pkey, a_read))
  298.         return_error(e_invalidaccess);
  299.         code = name_ref(pkey->value.bytes, r_size(pkey), &nref, 1);
  300.         if (code < 0)
  301.         return code;
  302.         nidx = name_index(&nref);
  303.     }
  304.     goto nh;
  305.     case t_real:
  306.     /*
  307.      * Make sure that equal reals and integers hash the same.
  308.      */
  309.     {
  310.         int expt;
  311.         double mant = frexp(pkey->value.realval, &expt);
  312.         /*
  313.          * The value is mant * 2^expt, where 0.5 <= mant < 1,
  314.          * or else expt == mant == 0.
  315.          */
  316.  
  317.         if (expt < sizeof(long) * 8 || pkey->value.realval == min_long)
  318.         hash = (uint)(int)pkey->value.realval * 30503;
  319.         else
  320.         hash = (uint)(int)(mant * min_long) * 30503;
  321.     }
  322.     goto ih;
  323.     case t_integer:
  324.     hash = (uint)pkey->value.intval * 30503;
  325.     ih:
  326.     kpack = packed_key_impossible;
  327.     ktype = -1;
  328.     nidx = 0;        /* only to pacify gcc */
  329.     break;
  330.     case t_null:        /* not allowed as a key */
  331.     return_error(e_typecheck);
  332.     default:
  333.     hash = r_btype(pkey) * 99;    /* yech */
  334.     kpack = packed_key_impossible;
  335.     ktype = -1;
  336.     nidx = 0;        /* only to pacify gcc */
  337.     }
  338.     /* Search the dictionary */
  339.     if (dict_is_packed(pdict)) {
  340.     const ref_packed *pslot = 0;
  341.  
  342.     packed_search_1(*ppvalue = packed_search_value_pointer,
  343.             return 1,
  344.             if (pslot == 0) pslot = kp, goto miss);
  345.     packed_search_2(*ppvalue = packed_search_value_pointer,
  346.             return 1,
  347.             if (pslot == 0) pslot = kp, goto miss);
  348.     /*
  349.      * Double wraparound, dict is full.
  350.      * Note that even if there was an empty slot (pslot != 0),
  351.      * we must return dictfull if length = maxlength.
  352.      */
  353.     if (pslot == 0 || d_length(pdict) == d_maxlength(pdict))
  354.         return_error(e_dictfull);
  355.     *ppvalue = pdict->values.value.refs + (pslot - kbot);
  356.     return 0;
  357.       miss:            /* Key is missing, not double wrap.  See above re dictfull. */
  358.     if (d_length(pdict) == d_maxlength(pdict))
  359.         return_error(e_dictfull);
  360.     if (pslot == 0)
  361.         pslot = kp;
  362.     *ppvalue = pdict->values.value.refs + (pslot - kbot);
  363.     return 0;
  364.     } else {
  365.     ref *kbot = pdict->keys.value.refs;
  366.     register ref *kp;
  367.     ref *pslot = 0;
  368.     int wrap = 0;
  369.  
  370.     for (kp = kbot + dict_hash_mod(hash, size) + 2;;) {
  371.         --kp;
  372.         if ((etype = r_type(kp)) == ktype) {    /* Fast comparison if both keys are names */
  373.         if (name_index(kp) == nidx) {
  374.             *ppvalue = pdict->values.value.refs + (kp - kbot);
  375.             return 1;
  376.         }
  377.         } else if (etype == t_null) {    /* Empty, deleted, or wraparound. */
  378.         /* Figure out which. */
  379.         if (kp == kbot) {    /* wrap */
  380.             if (wrap++) {    /* wrapped twice */
  381.             if (pslot == 0)
  382.                 return_error(e_dictfull);
  383.             break;
  384.             }
  385.             kp += size + 1;
  386.         } else if (r_has_attr(kp, a_executable)) {    /* Deleted entry, save the slot. */
  387.             if (pslot == 0)
  388.             pslot = kp;
  389.         } else        /* key not found */
  390.             break;
  391.         } else {
  392.         if (obj_eq(kp, pkey)) {
  393.             *ppvalue = pdict->values.value.refs + (kp - kbot);
  394.             return 1;
  395.         }
  396.         }
  397.     }
  398.     if (d_length(pdict) == d_maxlength(pdict))
  399.         return_error(e_dictfull);
  400.     *ppvalue = pdict->values.value.refs +
  401.         ((pslot != 0 ? pslot : kp) - kbot);
  402.     return 0;
  403.     }
  404. }
  405.  
  406. /*
  407.  * Look up a (constant) C string in a dictionary.
  408.  * Return 1 if found, <= 0 if not.
  409.  */
  410. int
  411. dict_find_string(const ref * pdref, const char *kstr, ref ** ppvalue)
  412. {
  413.     int code;
  414.     ref kname;
  415.  
  416.     if ((code = name_ref((const byte *)kstr, strlen(kstr), &kname, -1)) < 0)
  417.     return code;
  418.     return dict_find(pdref, &kname, ppvalue);
  419. }
  420.  
  421. /*
  422.  * Enter a key-value pair in a dictionary.
  423.  * See idict.h for the possible return values.
  424.  */
  425. int
  426. dict_put(ref * pdref /* t_dictionary */ , const ref * pkey, const ref * pvalue,
  427.      dict_stack_t *pds)
  428. {
  429.     dict *pdict = pdref->value.pdict;
  430.     gs_ref_memory_t *mem = dict_memory(pdict);
  431.     int rcode = 0;
  432.     int code;
  433.     ref *pvslot;
  434.  
  435.     /* Check the value. */
  436.     store_check_dest(pdref, pvalue);
  437.   top:if ((code = dict_find(pdref, pkey, &pvslot)) <= 0) {    /* not found *//* Check for overflow */
  438.     ref kname;
  439.     uint index;
  440.  
  441.     switch (code) {
  442.         case 0:
  443.         break;
  444.         case e_dictfull:
  445.         if (!dict_auto_expand)
  446.             return_error(e_dictfull);
  447.         code = dict_grow(pdref, pds);
  448.         if (code < 0)
  449.             return code;
  450.         goto top;    /* keep things simple */
  451.         default:        /* e_typecheck */
  452.         return code;
  453.     }
  454.     index = pvslot - pdict->values.value.refs;
  455.     /* If the key is a string, convert it to a name. */
  456.     if (r_has_type(pkey, t_string)) {
  457.         int code;
  458.  
  459.         if (!r_has_attr(pkey, a_read))
  460.         return_error(e_invalidaccess);
  461.         code = name_from_string(pkey, &kname);
  462.         if (code < 0)
  463.         return code;
  464.         pkey = &kname;
  465.     }
  466.     if (dict_is_packed(pdict)) {
  467.         ref_packed *kp;
  468.  
  469.         if (!r_has_type(pkey, t_name) ||
  470.         name_index(pkey) > packed_name_max_index
  471.         ) {        /* Change to unpacked representation. */
  472.         int code = dict_unpack(pdref, pds);
  473.  
  474.         if (code < 0)
  475.             return code;
  476.         goto top;
  477.         }
  478.         kp = pdict->keys.value.writable_packed + index;
  479.         if (ref_must_save_in(mem, &pdict->keys)) {    /* See initial comment for why it is safe */
  480.         /* not to save the change if the keys */
  481.         /* array itself is new. */
  482.         ref_do_save_in(mem, &pdict->keys, kp, "dict_put(key)");
  483.         }
  484.         *kp = pt_tag(pt_literal_name) + name_index(pkey);
  485.     } else {
  486.         ref *kp = pdict->keys.value.refs + index;
  487.  
  488.         if_debug2('d', "[d]0x%lx: fill key at 0x%lx\n",
  489.               (ulong) pdict, (ulong) kp);
  490.         store_check_dest(pdref, pkey);
  491.         ref_assign_old_in(mem, &pdict->keys, kp, pkey,
  492.                   "dict_put(key)");    /* set key of pair */
  493.     }
  494.     ref_save_in(mem, pdref, &pdict->count, "dict_put(count)");
  495.     pdict->count.value.intval++;
  496.     /* If the key is a name, update its 1-element cache. */
  497.     if (r_has_type(pkey, t_name)) {
  498.         name *pname = pkey->value.pname;
  499.  
  500.         if (pname->pvalue == pv_no_defn &&
  501.         pds && dstack_dict_is_permanent(pds, pdref) &&
  502.         /*
  503.          * Only set the cache if we aren't inside a save.
  504.          * This way, we never have to undo setting the cache.
  505.          */
  506.         !ref_saving_in(mem)
  507.         ) {        /* Set the cache. */
  508.         if_debug0('d', "[d]set cache\n");
  509.         pname->pvalue = pvslot;
  510.         } else {        /* The cache can't be used. */
  511.         if_debug0('d', "[d]no cache\n");
  512.         pname->pvalue = pv_other;
  513.         }
  514.     }
  515.     rcode = 1;
  516.     }
  517.     if_debug8('d', "[d]0x%lx: put key 0x%lx 0x%lx\n  value at 0x%lx: old 0x%lx 0x%lx, new 0x%lx 0x%lx\n",
  518.           (ulong) pdref->value.pdict,
  519.           ((const ulong *)pkey)[0], ((const ulong *)pkey)[1],
  520.           (ulong) pvslot,
  521.           ((const ulong *)pvslot)[0], ((const ulong *)pvslot)[1],
  522.           ((const ulong *)pvalue)[0], ((const ulong *)pvalue)[1]);
  523.     ref_assign_old_in(mem, &pdref->value.pdict->values, pvslot, pvalue,
  524.               "dict_put(value)");
  525.     return rcode;
  526. }
  527.  
  528. /*
  529.  * Enter a key-value pair where the key is a (constant) C string.
  530.  */
  531. int
  532. dict_put_string(ref * pdref, const char *kstr, const ref * pvalue,
  533.         dict_stack_t *pds)
  534. {
  535.     int code;
  536.     ref kname;
  537.  
  538.     if ((code = name_ref((const byte *)kstr, strlen(kstr), &kname, 0)) < 0)
  539.     return code;
  540.     return dict_put(pdref, &kname, pvalue, pds);
  541. }
  542.  
  543. /* Remove an element from a dictionary. */
  544. int
  545. dict_undef(ref * pdref, const ref * pkey, dict_stack_t *pds)
  546. {
  547.     gs_ref_memory_t *mem;
  548.     ref *pvslot;
  549.     dict *pdict;
  550.     uint index;
  551.  
  552.     if (dict_find(pdref, pkey, &pvslot) <= 0)
  553.     return (e_undefined);
  554.     /* Remove the entry from the dictionary. */
  555.     pdict = pdref->value.pdict;
  556.     index = pvslot - pdict->values.value.refs;
  557.     mem = dict_memory(pdict);
  558.     if (dict_is_packed(pdict)) {
  559.     ref_packed *pkp = pdict->keys.value.writable_packed + index;
  560.  
  561.     if_debug3('d', "[d]0x%lx: removing key at 0%lx: 0x%x\n",
  562.           (ulong)pdict, (ulong)pkp, (uint)*pkp);
  563.     /* See the initial comment for why it is safe not to save */
  564.     /* the change if the keys array itself is new. */
  565.     if (ref_must_save_in(mem, &pdict->keys))
  566.         ref_do_save_in(mem, &pdict->keys, pkp, "dict_undef(key)");
  567.     /*
  568.      * Accumulating deleted entries slows down lookup.
  569.      * Detect the easy case where we can use an empty entry
  570.      * rather than a deleted one, namely, when the next entry
  571.      * in the probe order is empty.
  572.      */
  573.     if (pkp[-1] == packed_key_empty) {
  574.         /*
  575.          * In this case we can replace any preceding deleted keys with
  576.          * empty ones as well.
  577.          */
  578.         uint end = nslots(pdict);
  579.  
  580.         *pkp = packed_key_empty;
  581.         while (++index < end && *++pkp == packed_key_deleted)
  582.         *pkp = packed_key_empty;
  583.     } else
  584.         *pkp = packed_key_deleted;
  585.     } else {            /* not packed */
  586.     ref *kp = pdict->keys.value.refs + index;
  587.  
  588.     if_debug4('d', "[d]0x%lx: removing key at 0%lx: 0x%lx 0x%lx\n",
  589.           (ulong)pdict, (ulong)kp, ((ulong *)kp)[0], ((ulong *)kp)[1]);
  590.     make_null_old_in(mem, &pdict->keys, kp, "dict_undef(key)");
  591.     /*
  592.      * Accumulating deleted entries slows down lookup.
  593.      * Detect the easy case where we can use an empty entry
  594.      * rather than a deleted one, namely, when the next entry
  595.      * in the probe order is empty.
  596.      */
  597.     if (!r_has_type(kp - 1, t_null) ||    /* full entry */
  598.         r_has_attr(kp - 1, a_executable)    /* deleted or wraparound */
  599.         )
  600.         r_set_attrs(kp, a_executable);    /* mark as deleted */
  601.     }
  602.     ref_save_in(mem, pdref, &pdict->count, "dict_undef(count)");
  603.     pdict->count.value.intval--;
  604.     /* If the key is a name, update its 1-element cache. */
  605.     if (r_has_type(pkey, t_name)) {
  606.     name *pname = pkey->value.pname;
  607.  
  608.     if (pv_valid(pname->pvalue)) {
  609. #ifdef DEBUG
  610.         /* Check the the cache is correct. */
  611.         if (!(pds && dstack_dict_is_permanent(pds, pdref)))
  612.         lprintf1("dict_undef: cached name value pointer 0x%lx is incorrect!\n",
  613.              (ulong) pname->pvalue);
  614. #endif
  615.         /* Clear the cache */
  616.         pname->pvalue = pv_no_defn;
  617.     }
  618.     }
  619.     make_null_old_in(mem, &pdict->values, pvslot, "dict_undef(value)");
  620.     return 0;
  621. }
  622.  
  623. /* Return the number of elements in a dictionary. */
  624. uint
  625. dict_length(const ref * pdref /* t_dictionary */ )
  626. {
  627.     return d_length(pdref->value.pdict);
  628. }
  629.  
  630. /* Return the capacity of a dictionary. */
  631. uint
  632. dict_maxlength(const ref * pdref /* t_dictionary */ )
  633. {
  634.     return d_maxlength(pdref->value.pdict);
  635. }
  636.  
  637. /* Return the maximum index of a slot within a dictionary. */
  638. uint
  639. dict_max_index(const ref * pdref /* t_dictionary */ )
  640. {
  641.     return npairs(pdref->value.pdict) - 1;
  642. }
  643.  
  644. /* Copy one dictionary into another. */
  645. /* If new_only is true, only copy entries whose keys */
  646. /* aren't already present in the destination. */
  647. int
  648. dict_copy_entries(const ref * pdrfrom /* t_dictionary */ ,
  649.           ref * pdrto /* t_dictionary */ , bool new_only,
  650.           dict_stack_t *pds)
  651. {
  652.     int space = r_space(pdrto);
  653.     int index;
  654.     ref elt[2];
  655.     ref *pvslot;
  656.     int code;
  657.  
  658.     if (space != avm_max) {    /* Do the store check before starting the copy. */
  659.     index = dict_first(pdrfrom);
  660.     while ((index = dict_next(pdrfrom, index, elt)) >= 0)
  661.         if (!new_only || dict_find(pdrto, &elt[0], &pvslot) <= 0) {
  662.         store_check_space(space, &elt[0]);
  663.         store_check_space(space, &elt[1]);
  664.         }
  665.     }
  666.     /* Now copy the contents. */
  667.     index = dict_first(pdrfrom);
  668.     while ((index = dict_next(pdrfrom, index, elt)) >= 0) {
  669.     if (new_only && dict_find(pdrto, &elt[0], &pvslot) > 0)
  670.         continue;
  671.     if ((code = dict_put(pdrto, &elt[0], &elt[1], pds)) < 0)
  672.         return code;
  673.     }
  674.     return 0;
  675. }
  676.  
  677. /* Resize a dictionary. */
  678. int
  679. dict_resize(ref * pdref, uint new_size, dict_stack_t *pds)
  680. {
  681.     dict *pdict = pdref->value.pdict;
  682.     gs_ref_memory_t *mem = dict_memory(pdict);
  683.     uint new_mask = imemory_new_mask(mem);
  684.     dict dnew;
  685.     ref drto;
  686.     int code;
  687.  
  688.     if (new_size < d_length(pdict)) {
  689.     if (!dict_auto_expand)
  690.         return_error(e_dictfull);
  691.     new_size = d_length(pdict);
  692.     }
  693.     make_tav(&drto, t_dictionary, r_space(pdref) | a_all | new_mask,
  694.          pdict, &dnew);
  695.     dnew.memory = pdict->memory;
  696.     if ((code = dict_create_contents(new_size, &drto, dict_is_packed(pdict))) < 0)
  697.     return code;
  698.     /* We must suppress the store check, in case we are expanding */
  699.     /* systemdict or another global dictionary that is allowed */
  700.     /* to reference local objects. */
  701.     r_set_space(&drto, avm_local);
  702.     dict_copy(pdref, &drto, pds);    /* can't fail */
  703.     /* Save or free the old dictionary. */
  704.     if (ref_must_save_in(mem, &pdict->values))
  705.     ref_do_save_in(mem, pdref, &pdict->values, "dict_resize(values)");
  706.     else
  707.     gs_free_ref_array(mem, &pdict->values, "dict_resize(old values)");
  708.     if (ref_must_save_in(mem, &pdict->keys))
  709.     ref_do_save_in(mem, pdref, &pdict->keys, "dict_resize(keys)");
  710.     else
  711.     gs_free_ref_array(mem, &pdict->keys, "dict_resize(old keys)");
  712.     ref_assign(&pdict->keys, &dnew.keys);
  713.     ref_assign(&pdict->values, &dnew.values);
  714.     ref_save_in(dict_memory(pdict), pdref, &pdict->maxlength,
  715.         "dict_resize(maxlength)");
  716.     d_set_maxlength(pdict, new_size);
  717.     if (pds)
  718.     dstack_set_top(pds);    /* just in case this is the top dict */
  719.     return 0;
  720. }
  721.  
  722. /* Grow a dictionary for dict_put. */
  723. int
  724. dict_grow(ref * pdref, dict_stack_t *pds)
  725. {
  726.     dict *pdict = pdref->value.pdict;
  727.     /* We might have maxlength < npairs, if */
  728.     /* dict_round_size increased the size. */
  729.     ulong new_size = (ulong) d_maxlength(pdict) * 3 / 2 + 2;
  730.  
  731. #if arch_sizeof_int < arch_sizeof_long
  732.     if (new_size > max_uint)
  733.     new_size = max_uint;
  734. #endif
  735.     if (new_size > npairs(pdict)) {
  736.     int code = dict_resize(pdref, (uint) new_size, pds);
  737.  
  738.     if (code >= 0)
  739.         return code;
  740.     /* new_size was too big. */
  741.     if (npairs(pdict) < dict_max_size) {
  742.         code = dict_resize(pdref, dict_max_size, pds);
  743.         if (code >= 0)
  744.         return code;
  745.     }
  746.     if (npairs(pdict) == d_maxlength(pdict)) {    /* Can't do it. */
  747.         return code;
  748.     }
  749.     /* We can't grow to new_size, but we can grow to npairs. */
  750.     new_size = npairs(pdict);
  751.     }
  752.     /* maxlength < npairs, we can grow in place */
  753.     ref_save_in(dict_memory(pdict), pdref, &pdict->maxlength,
  754.         "dict_put(maxlength)");
  755.     d_set_maxlength(pdict, new_size);
  756.     return 0;
  757. }
  758.  
  759. /* Prepare to enumerate a dictionary. */
  760. int
  761. dict_first(const ref * pdref)
  762. {
  763.     return (int)nslots(pdref->value.pdict);
  764. }
  765.  
  766. /* Enumerate the next element of a dictionary. */
  767. int
  768. dict_next(const ref * pdref, int index, ref * eltp /* ref eltp[2] */ )
  769. {
  770.     dict *pdict = pdref->value.pdict;
  771.     ref *vp = pdict->values.value.refs + index;
  772.  
  773.     while (vp--, --index >= 0) {
  774.     array_get(&pdict->keys, (long)index, eltp);
  775.     /* Make sure this is a valid entry. */
  776.     if (r_has_type(eltp, t_name) ||
  777.         (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
  778.         ) {
  779.         eltp[1] = *vp;
  780.         if_debug6('d', "[d]0x%lx: index %d: %lx %lx, %lx %lx\n",
  781.               (ulong) pdict, index,
  782.               ((ulong *) eltp)[0], ((ulong *) eltp)[1],
  783.               ((ulong *) vp)[0], ((ulong *) vp)[1]);
  784.         return index;
  785.     }
  786.     }
  787.     return -1;            /* no more elements */
  788. }
  789.  
  790. /* Return the index of a value within a dictionary. */
  791. int
  792. dict_value_index(const ref * pdref, const ref * pvalue)
  793. {
  794.     return (int)(pvalue - pdref->value.pdict->values.value.refs - 1);
  795. }
  796.  
  797. /* Return the entry at a given index within a dictionary. */
  798. /* If the index designates an unoccupied entry, return e_undefined. */
  799. int
  800. dict_index_entry(const ref * pdref, int index, ref * eltp /* ref eltp[2] */ )
  801. {
  802.     const dict *pdict = pdref->value.pdict;
  803.  
  804.     array_get(&pdict->keys, (long)(index + 1), eltp);
  805.     if (r_has_type(eltp, t_name) ||
  806.     (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
  807.     ) {
  808.     eltp[1] = pdict->values.value.refs[index + 1];
  809.     return 0;
  810.     }
  811.     return e_undefined;
  812. }
  813.